package C023;

import java.util.Arrays;

/**
 * ClassName: RandomFastSorting
 * Package: C023
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/9 14:33
 * @Version 1.0
 * @Since 1.0
 */
public class RandomFastSorting {
    public static void main(String[] args) {
        int n = 10000;
        int size = 100;
        int length = 20;
        for (int i = 0; i < n; i++) {
            int[] arr1 = randomGenerateArr(size, length);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            int[] arr4 = Arrays.copyOf(arr1, arr1.length);
            quickSort(arr1, 0, arr1.length - 1);
            Arrays.sort(arr2);
            quickSort2(arr3, 0, arr3.length - 1);
            if(!Arrays.equals(arr1, arr2) || !Arrays.equals(arr3, arr1)) {
                System.out.println("error !!!");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr3));
                System.out.println(Arrays.toString(arr4));
                return;
            }
        }

        System.out.println("success !!!");
    }

    public static int[] randomGenerateArr(int size, int length) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = (int) (Math.random() * size);
        }
        return ints;
    }


    /**
     * 快速排序
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort(int[] arr, int l, int r) {
        if(l >= r) {
            return;
        }
        int randomIndex = l + (int)(Math.random() * (r - l)) + 1; // l ... r
        int mid = partitionForTwo(arr, l, r, randomIndex);
        quickSort(arr, l, mid - 1);
        quickSort(arr, mid + 1, r);
    }

    /**
     * 两区划分
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionForTwo(int[] arr, int l, int r, int index) {
        int m = l;
        int index2 = 0;
        int num = arr[index];
        for (int i = l; i <= r; i++) {
            if(arr[i] <= num) {
                if(arr[i] == num) {
                    index2 = m;
                }
                swap(arr, m, i);
                m ++;
            }
        }
        swap(arr, index2, m - 1);
        return m - 1;
    }

    private static void swap(int[] arr, int m, int i) {
        int temp = arr[m];
        arr[m] = arr[i];
        arr[i] = temp;
    }


    public static void quickSort2(int[] arr, int l, int r) {
        if(l >= r) {
            return;
        }
        int randomIndex = l + (int)(Math.random() * (r - l + 1));
        int[] mids = partitionForThree(arr, l, r, randomIndex);
        quickSort2(arr, l, mids[0]);
        quickSort2(arr, mids[1], r);
    }

    /**
     * 三区划分
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int[] partitionForThree(int[] arr, int l, int r, int index) {
        int ml = l;
        int mr = r;
        int num = arr[index];
        int i = l;
        while(i <= mr) {
            if(arr[i] < num) {
                swap(arr, ml ++, i ++);
            }else if(arr[i] == num) {
                i ++;
            }else if(arr[i] > num) {
                swap(arr, mr --, i);
            }
        }
        return new int[]{ml - 1, mr + 1};
    }


}
